﻿//#include <iostream>//4牛牛的快递
//#include<cmath>
//using namespace std;
//
//int main() {
//    float a;
//    char b;
//    int ret = 0;
//    cin >> a >> b;
//    if (a <= 1)
//        ret = 20;
//    else
//        ret = 20 + ceil(a - 1);//ceil函数向下取整
//    if (b == 'y')
//        ret += 5;
//    cout << ret << endl;
//}
//// 64 位输出请用 printf("%lld")
//class Solution {//5最小花费爬楼梯
//public:
//    
//    int minCostClimbingStairs(vector<int>& cost) {
//        // write code here
//        int n = cost.size();
//        vector<int> dp(n + 1);
//        for (int i = 2;i <= n;i++) {
//            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
//        }
//        return dp[n];
//    }
//
//};



//#include <bits/stdc++.h>//6.数组中两个字符串的最小距离
//using namespace std;
//int n;
//string s1, s2;
//int main()
//{
//	string s;
//	cin >> n;
//	cin >> s1 >> s2;
//	int prev1 = -1, prev2 = -1, ret = 0x3f3f3f3f;
//	for (int i = 0; i < n; i++)//⽤ prev1 标记 i 位置之前最近⼀次出现的第⼀个字符串的下标；
//	{//⽤ prev2 标记 i 位置之前最近⼀次出现的第二个字符串的下标；
//		cin >> s;
//		if (s == s1) // 去前⾯找最近的 s2 
//		{
//			if (prev2 != -1)
//			{
//				ret = min(ret, i - prev2);
//			}
//			prev1 = i;
//		}
//		else if (s == s2) // 去前⾯找 s1
//		{
//			if (prev1 != -1)
//			{
//				ret = min(ret, i - prev1);
//			}
//			prev2 = i;
//		}
//	}
//	if (ret == 0x3f3f3f3f) cout << -1 << endl;
//	else cout << ret << endl;
//	return 0;
//}

class Solution {//leetcode 图像渲染
	int dx[4] = { 0,0,1,-1 };
	int dy[4] = { 1,-1,0,0 };
	typedef pair<int, int> PII;
public:

	vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
		int prev = image[sr][sc];//先将需要修改的像素值标记
		int m = image.size(), n = image[0].size();
		if (prev == color) return image;
		queue<PII> q;//队列存一个数对
		q.push({ sr,sc });//将初始位置传入，
		while (q.size()) {//当队列中还有数对时，
			auto [a, b] = q.front();//用a,b存到上一个的位置坐标，
			q.pop();//弹出
			image[a][b] = color;//将该位置像素值修改，
			for (int i = 0;i < 4;i++) {//移动坐标向四周
				int x = a + dx[i], y = b + dy[i];//
				if (x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev)//判断越界和下一个位置是否和上一个位置颜色相同
					q.push({ x,y });//颜色相同，入队列
			}
		}
		return image;
	}
};